package com.hzj.alg;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 迭代思想
 * 深度优先算法与广度优先算法
 */
public class letterCombinations {
    public static void main(String[] args) {
        List<String> list = new letterCombinations().letterCombinations("23");
        System.out.println(list);
    }
    public List<String > letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character,String > phoneMap = new HashMap<>(){{
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }};
        backtrack1(combinations,phoneMap,digits,0,new StringBuffer());
        return combinations;

    }
    public void backtrack(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuffer combination) {
        if (index == digits.length()){
            combinations.add(combination.toString());
            System.out.println("***");
            System.out.println(combination.toString());
        }else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            System.out.println("****");
            System.out.println(letters);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations,phoneMap,digits,index + 1,combination);
                System.out.println("第" + i + "遍循环中index的值" + index);
                combination.deleteCharAt(index);
            }
        }
    }
    public void backtrack1(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        }else {
            char c = digits.charAt(index);

            String s = phoneMap.get(c);
            int length = s.length();
            for (int i = 0; i < length; i++) {
                combination.append(s.charAt(i));
                backtrack1(combinations,phoneMap,digits,index + 1,combination);
                combination.deleteCharAt(index);
            }
        }
    }
    }

